//
// Created by 66477 on 2022/10/5.
//

#ifndef DATA_STRUCTURE_BITREE5_3_H
#define DATA_STRUCTURE_BITREE5_3_H

#include "Node5_3.h"
#include "stack"
#include <vector>

using namespace std;

class BiTree5_3 {
private:
    Node5_3 *root = nullptr;

    Node5_3 *createNodeDLR(string s, int *i) {
        if (*i >= s.length()) {
            (*i)++;
            cout << "input string exception" << endl;
            return nullptr;
        } else if (s[*i] == '#') {
            (*i)++;
            return nullptr;
        } else {
            Node5_3 *node = new Node5_3(s[*i]);
            (*i)++;
            node->setLChild(createNodeDLR(s, i));
            node->setRChild(createNodeDLR(s, i));
            return node;
        }
    }

    static bool haveNode(vector<Node5_3 *> vector, Node5_3 *node) {
        for (int i = 0; i < vector.size(); ++i) {
            if (vector[i] == node) {
                return true;
            }
        }
        return false;
    }

public:
    BiTree5_3(string s) {
        int i;
        root = createNodeDLR(s, &i);
    }

    void printDLR() {
        stack<Node5_3 *> sta;
        Node5_3 *node;
        if (root == nullptr) return;
        sta.push(root);
        while (!sta.empty()) {
            node = sta.top();
            sta.pop();
            cout << node->getData();
            if (node->getRChild() != nullptr) {
                sta.push(node->getRChild());
            }
            if (node->getLChild() != nullptr) {
                sta.push(node->getLChild());
            }
        }
        cout << endl;
    }

    void printLDR() {
        if (root == nullptr) return;
        stack<Node5_3 *> sta;
        Node5_3 *node = root;
        while (!sta.empty() || node != nullptr) {
            while (node != nullptr) {
                sta.push(node);
                node = node->getLChild();
            }
            if (!sta.empty()) {
                cout << sta.top()->getData();
                node = sta.top()->getRChild();
                sta.pop();
            }
        }
        cout << endl;
    }

    void printLRD() {
        stack<Node5_3 *> *sta = new stack<Node5_3 *>();
        Node5_3 *node;
        sta->push(root);
        vector<Node5_3 *> *vec = new vector<Node5_3 *>();
        while (!sta->empty()) {
            node = sta->top();
            if (node->getLChild() != nullptr && !haveNode(*vec, node->getLChild())) {
                sta->push(node->getLChild());
                vec->push_back(node->getLChild());
            } else {
                if (node->getRChild() != nullptr && !haveNode(*vec, node->getRChild())) {
                    sta->push(node->getRChild());
                    vec->push_back(node->getRChild());
                } else {
                    cout << sta->top()->getData();
                    sta->pop();
                }
            }
        }
        cout << endl;
    }
};

#endif //DATA_STRUCTURE_BITREE5_3_H
